package practice_2025_7_14;

import practice_2025_9.practice_9_5.ListNode;

import java.util.*;

public class Solution {
    /**
     * 合并 k 个升序列表
     * @param lists
     * @return
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        int k = lists.length;
        ListNode head = new ListNode();
        if (k == 0) return head.next;
        ListNode cur = head;
        while(true) {
            // 找到最小值
            int nextIndex  = findMin(lists);
            // System.out.println("next: " + next);
            if (nextIndex == -1) {
                break;
            } else {
                cur.next = lists[nextIndex];
                cur = cur.next;
                lists[nextIndex] = lists[nextIndex].next;
            }
        }
        return head.next;
    }
    public int findMin(ListNode[] lists) {
        int min = -1;
        int minValue = Integer.MAX_VALUE;
        for(int i = 0; i < lists.length; i++) {
            if (lists[i] != null && lists[i].val < minValue) {
                minValue = lists[i].val;
                min = i;
            }
        }
        return min;
    }

    /**
     * 利用堆进行排序
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for(int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                priorityQueue.add(lists[i]);
            }
        }
        ListNode head = new ListNode();
        ListNode cur = head;
        while(!priorityQueue.isEmpty()) {
            ListNode min = priorityQueue.poll();
            cur.next = min;
            cur = cur.next;
            if (min.next != null) {
                priorityQueue.add(min.next);
            }
        }
        return head.next;
    }

    /**
     * k 个一组翻转链表
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode newHead = new ListNode();
        ListNode cur = head;
        ListNode cur1 = newHead;
        int size = 0;
        while(cur != null) {
            cur = cur.next;
            size++;
        }
        if (size < k) return head;
        int count = size / k;
        cur = head;
        //  System.out.println(count +" cur: " + cur.val);
        while(count > 0) {
            ListNode head1 = new ListNode();
            // 翻转
            int i = 0;
            ListNode next1 = cur;
            while(i < k) {
                //    System.out.println(" cur" + cur.val);
                ListNode next = head1.next;
                head1.next = cur;
                cur = cur.next;
                head1.next.next = next;
                i++;
            }
            cur1.next = head1.next;
            cur1 = next1;
            count--;
        }
        cur1.next = cur;
        return newHead.next;
    }

    /**
     * 存在重复元素II
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        String s = "abc";

        for(int i = 0; i < nums.length; i++) {
            if (hash.containsKey(nums[i])) {
                if (k >= Math.abs(i - hash.get(nums[i]))) {
                    return true;
                }
                hash.put(nums[i], i);
            } else {
                hash.put(nums[i], i);
            }
        }
        return false;
    }

    /**
     * 字母异位词分组
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();
        for(int i = 0; i < strs.length; i++) {
            // 按照字典序排列
            char[] key = strs[i].toCharArray();
            Arrays.sort(key);
            String sort = new String(key);
            List<String> list = hash.getOrDefault(sort, new ArrayList<String>());
            list.add(strs[i]);
            hash.put(sort, list);
        }
        List<List<String>> res = new ArrayList<>();
        for(String key: hash.keySet()) {
            res.add(hash.get(key));
        }
        return res;
    }
}

